package org.schat;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Description 回溯算法
 * @Author lsh
 * @Date 2020/3/25 13:36
 **/
public class BackTrack {

    public static void main(String[] args){
        int[] nums = {1,2,3};
        List<List<Integer>> ans = premute(nums);
        for(List<Integer> track : ans){
            System.out.println(Arrays.toString(track.toArray()));
        }
    }

    public static List<List<Integer>> premute(int[] nums){
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> track = new ArrayList<>();
        backTrack(nums,track,ans);
        return ans;
    }

    public static void backTrack(int[] nums,List<Integer> track,List<List<Integer>> ans){
        if(track.size() == nums.length){
            ans.add(new ArrayList<Integer>(track));
        }else{
            for(int i = 0; i< nums.length;i++){
                //决策路径中已选中的元素不能再次选择了
                if(track.contains(nums[i]))continue;
                // choose
                track.add(nums[i]);
                backTrack(nums,track,ans);
                // unchoose
                track.remove(track.size() -1);
            }
        }

    }

}
